package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/11 13:48

 丑数：1是，因子含2,3,5的都是丑数
 输入n，返回从1开始的第n个丑数

 优先队列维护一个小根堆保证从1按序开始，
 核心：取出元素后与2,3,5做乘法，——逆向思维：不求某个数的因数，而是通过乘积构造，更好实现
 当然如何一个个检查因子也能实现，但是复杂度高:
     while (n % 2) == 0:        #将质因子2全部除干净
            n /= 2
        while (n % 3) == 0:        #将质因子3全部除干净
            n /= 3
        while (n % 5) == 0:        #将质因子5全部除干净
            n /= 5
        return n == 1              #如果最终结果为1说明该数n是丑数
 如果不重复(2*3  3*2)就放入堆和集合
 */

import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class Main20 {
    public int GetUglyNumber_Solution(int index) {
        if(index==0)return 0;
        Set<Long> set=new HashSet<>();
        //默认为小根堆
        PriorityQueue<Long>queue=new PriorityQueue<Long>();

        int factor[]={2,3,5};
        queue.offer(1L);
        set.add(1L);
        Long ans=0L;
        for(int i=0;i<index;++i){
            ans=queue.poll();
            for(int j=0;j<3;++j){
                Long now=factor[j]*ans;
                if(!set.contains(now)){
                    queue.offer(now);
                    set.add(now);
                }
            }
        }
        return ans.intValue();
    }
    public static void main(String[] args) {

    }
}
